/**
 * 2016年10月30日
 */
package algorithm;


/**
 * @author Alex
 *
 */
public class MatrixPath {
	static class Solution {
	    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
	    {
	    	return get(matrix,rows,cols,str);
	    }
	    
	    boolean get(char[] matrix, int rows, int cols, char[] str){
	        if(matrix == null || rows == 0 || cols == 0 ) return false;
	        if(str==null || str.length==0) return true;
	        boolean [][]visited = new boolean[rows][cols];
	        reset(visited);
	        for(int i=0;i<rows;i++){
	            for(int j =0;j<cols;j++){
	                if(core(matrix,rows,cols,i,j,0,str,(boolean[][])visited.clone())){
	                    return true;
	                }
	            }
	        }    
	        return false;    
			        
	    }
	    boolean core(char matrix[],int rows,int cols,int r,int c,int cur,char str[],boolean visited[][]){
	    	if(cur == str.length) return true;
	    	if(r==rows || c==cols || r<0 || c<0) return false;
	        if(visited[r][c]) return false;
	        if(matrix[r*cols+c] == str[cur]){
	           	visited[r][c] = true;
	            boolean flag = false;
	            //右 下 上 左
	            flag = core(matrix,rows,cols,r,c+1,cur+1,str,visited) ||core(matrix,rows,cols,r+1,c,cur+1,str,visited)|| core(matrix,rows,cols,r-1,c,cur+1,str,visited) || core(matrix,rows,cols,r,c-1,cur+1,str,visited);
	            if(!flag){
	            	visited[r][c] = false;
	            }
	            return flag;
	        }else{
	            return false;
	        }
	        
	        
	    }
	    void reset(boolean v[][]){
	        for(int i=0;i<v.length;i++){
	            for(int j=0;j<v[0].length;j++){
	                v[i][j] = false;
	            }
	        }
	    }


	}


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		char matrix []= {'A'}; 
		char str  [] = {'A'};
		System.out.println(s.hasPath(matrix, 1, 1, str));

	}

}
